package org.example.myleet.p1646;

public class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int max = 0;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int end = n / 2;
        for (int i = 1; i <= end; ++i) {
            int idxEven = 2 * i;
            nums[idxEven] = nums[i];
            max = Math.max(max, nums[2 * i]);
            int idxOdd = 2 * i + 1;
            if (idxOdd <= n) {
                nums[idxOdd] = nums[i] + nums[i + 1];
                max = Math.max(max, nums[idxOdd]);
            }
        }
        return max;
    }
}
